package MyDoublyLinkedList;

public class MyDoublyLinkedList implements Operations{

    MyDoublyLinkedListNode headNode;//头节点
    MyDoublyLinkedListNode lastNode;//尾结点

    @Override
    public void display() {
        MyDoublyLinkedListNode curNode = headNode;

        while (curNode != null) {
            System.out.print(curNode.val + " ");
            curNode = curNode.nextNode;
        }
        System.out.println();
    }

    @Override
    public void addFirst(int data) {

        MyDoublyLinkedListNode newNode = new MyDoublyLinkedListNode(data);

        if (headNode == null) {
            headNode = newNode;
            lastNode = newNode;
        } else {
            newNode.nextNode = headNode;
            headNode.prevNode = newNode;
            headNode = newNode;
        }

    }

    @Override
    public void addLast(int data) {
        if (headNode == null) {
            addFirst(data);
        } else {
            MyDoublyLinkedListNode newNode = new MyDoublyLinkedListNode(data);

            newNode.prevNode = lastNode;
            lastNode.nextNode = newNode;
            lastNode = newNode;
        }

    }

    @Override
    public void addIndex(int index, int data) {

        if (headNode == null && index != 0) {
            throw new EmptyListException("空链表只能在0号结点插入数据");
        } else if (index == 0) {
            addFirst(data);
        } else if (index == size()) {
            addLast(data);
        } else {

            if (index < 0 || index > size()) {
                throw new IndexException("下标不合法");
            }
            MyDoublyLinkedListNode curNode = headNode;

            while (index != 0) {
                curNode = curNode.nextNode;
                index--;
            }

            MyDoublyLinkedListNode newNode = new MyDoublyLinkedListNode(data);

            newNode.nextNode = curNode;
            newNode.prevNode = curNode.prevNode;
            curNode.prevNode.nextNode = newNode;
            curNode.prevNode = newNode;
        }
    }

    @Override
    public boolean contains(int key) {
        MyDoublyLinkedListNode curNode = headNode;

        while (curNode != null) {
            if (curNode.val == key) {
                return true;
            }
            curNode = curNode.nextNode;
        }

        return false;
    }

    @Override
    public void remove(int key) {

        if (headNode == null) {
            throw new EmptyListException("空链表无法删除数据");
        }

        MyDoublyLinkedListNode curNode = headNode;

        while (curNode != null) {
            if (curNode.val == key) {
                if (curNode == headNode) {
                    headNode = headNode.nextNode;
                    headNode.prevNode = null;
                    return;
                } else if (curNode == lastNode) {
                    lastNode = lastNode.prevNode;
                    lastNode.nextNode = null;
                } else {
                    curNode.prevNode.nextNode = curNode.nextNode;
                    curNode.nextNode.prevNode = curNode.prevNode;
                    return;
                }
            }
            curNode = curNode.nextNode;
        }

    }

    @Override
    public void removeAllKey(int key) {

        if (headNode == null) {
            throw new EmptyListException("空链表无法删除数据");
        }

//        while (headNode.val == key) {
//            headNode = headNode.nextNode;
//            headNode.prevNode = null;
//        }
//
//        while (lastNode.val == key) {
//            lastNode = lastNode.prevNode;
//            lastNode.nextNode = null;
//        }

        MyDoublyLinkedListNode curNode = headNode.nextNode;

        while (curNode != lastNode) {
            if (curNode.val == key) {
                curNode.prevNode.nextNode = curNode.nextNode;
                curNode.nextNode.prevNode = curNode.prevNode;
            }
            curNode = curNode.nextNode;
        }

        if (headNode.val == key) {
            headNode = headNode.nextNode;
            headNode.prevNode = null;
        }

        if (lastNode.val == key) {
            lastNode = lastNode.prevNode;
            if (lastNode == null) {
                headNode = null;
            } else {
                lastNode.nextNode = null;
            }
        }
    }

    @Override
    public int size() {
        int len = 0;
        MyDoublyLinkedListNode curNode = headNode;

        while (curNode != null) {
            len++;
            curNode = curNode.nextNode;
        }

        return len;
    }

    @Override
    public void clear() {
        MyDoublyLinkedListNode curNode = headNode;

        while (headNode != null) {
            headNode = headNode.nextNode;
            curNode = null;
            curNode = headNode;
        }
    }

    //现有一链表的头指针 ListNode* pHead，给一定值x
    //编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
    public static MyDoublyLinkedListNode partition(MyDoublyLinkedListNode pHead, int x) {
        // write code here

        MyDoublyLinkedListNode smallNode = new MyDoublyLinkedListNode(-1);
        MyDoublyLinkedListNode lagerNode = new MyDoublyLinkedListNode(-1);
        MyDoublyLinkedListNode curNode = pHead;

        MyDoublyLinkedListNode sn = smallNode;
        MyDoublyLinkedListNode ln = lagerNode;

        while (curNode != null) {
            if (curNode.val < x) {
                sn.nextNode = curNode;
                sn = sn.nextNode;
            } else {
                ln.nextNode = curNode;
                ln = ln.nextNode;
            }
            curNode = curNode.nextNode;
        }

        if (smallNode.nextNode == null) {
            sn.nextNode = null;
            return lagerNode.nextNode;
        }

        if (lagerNode.nextNode == null) {
            ln.nextNode = null;
            return smallNode.nextNode;
        }

        sn.nextNode = lagerNode.nextNode;
        ln.nextNode = null;

        return smallNode.nextNode;
    }
}
